Computer systems are often interconnected by computer networks for the purpose of communicating information. Computer systems connected on such networks communicate with each other by sending information through their electronic connections over media such as fiber or copper cabling, air, network communication systems such as routers, and any combination thereof using one or more communication protocols such as TCP/IP, for example. Networks can be organized into various types of topologies.
FIG. 1 illustrates one such topology that includes a network 100 having several networks 101-102 (e.g., local area networks (LANs)) that are coupled by a routing system 103. Computer systems of each local area network are connected to communications links 101a-101b. When a source computer system on a local area network 101 or 102 sends information to a destination computer system on the same network 101 or 102, the source computer system prepares a message (e.g., frame, packet, cell, or the like) that includes the address of the destination computer system and transmits the message on the communications link 101a or 102a. Other computer systems on that same local area network 101 or 102 (i.e., connected to the communications link 101a or 102a) reads the message that was transmitted. The destination computer system detects that its address is included in that message, and it processes the message accordingly.
Routing systems are generally used to couple one or more local networks to other networks (e.g., other public or private networks (e.g., the Internet, corporate network, etc.)). A routing system 103 is typically a dedicated special-purpose computer system to which each network 101, 102 is coupled, and routes information between these networks. The routing system 103 maintains routing information that identifies the location of other networks. In a TCP/IP routed network, for example, routing system 103 monitors packets sent on each network 101-102 to detect when a computer system on one network 101-102 is sending a packet to a computer system on another network (e.g., networks 101 or 102). When the routing system 103 detects such a packet, it forwards that packet onto the communications link 101a or 102a for the network 101 or 102 to which the destination computer system is connected. In this way, the routing system 103 interconnects networks 101 and 102 into an overall network 100. Similar routing techniques may be used, for example, to interconnect local area networks (LANs), wide area networks (WANs), and the Internet 104.
Routers make forwarding decisions based on local information stored in the router that identifies a next “hop” based on the destination of a packet. That is, the router generally forwards a packet out an interface to one or more other systems based on the destination address of the packet.
Routers communicate among each other to share information regarding the networks to which they are connected. This communication causes routers to update their local databases with this communicated information. Generally, routers maintain routing tables that store entries regarding the networks to which the router can communicate. Communication between routers is performed according to a method referred to in the art as a routing protocol. There are many different types of routing protocols used for sharing routing information among computer systems. For the TCP/IP protocol, for example, there are numerous routing protocols including Border Gateway Protocol (BGP), Routing Information Protocol (RIP), Open Shortest Path First (OSPF), Interior Gateway Routing Protocol (IGRP) and Enhanced Interior Gateway Routing Protocol (EIGRP) and others. An organization may implement one or more routing protocols within any network.
Due to the scale of communication networks such as the Internet, there are two types of routing protocols, intradomain and interdomain protocols, referred to in the art as Interior Gateway Protocols (IGPs) and Exterior Gateway Protocols (EGPs), respectively. Intradomain routing protocols are generally run in networks that are limited in scope and have a single administrative domain. Inter-domain routing protocols are used at the borders of administrative domains, where network entities of different organizations share information that identifies network addresses that may be reached through that network. For example, one network provider (e.g., an Internet Service Provider (ISP)) may indicate, via a routing protocol, which networks are reachable through the provider's network. The predominant protocol used in the Internet today is the Border Gateway Protocol (BGP). BGP may be used as either an intradomain or interdomain routing protocol.
FIG. 2 shows a functional block diagram of a network 101 that includes a number of networks (e.g., ISP networks) coupled together by a computer network. Each of the ISPs can include a number of systems 100 that are similar to that shown in FIG. 1, which are coupled together over the Internet. The wide area network 101 of FIG. 2 further shows a number of clients 105 coupled to ISP7 and servers 106 coupled to ISP1 and ISP2. Clients 105 can include a number of personal computers 105a, 105b and 105c that are adapted to receive information from a plurality of web pages or other information from the server 106, as well as web pages or other information from other computer systems (not shown), which are also coupled to the network shown in FIG. 2.
Server 106 can include a number of computer subsystems 106a, 106b, 106c, 106d and 106e, as well as associated databases (not shown). For example, server 106 may include, for example, a group of servers (e.g., server farm) configured to respond to requests for information received over a network. The computer subsystems 106a, 106b, 106c, 106d and 106e may be, for example, web servers of a web page hosting site that are adapted to store and retrieve a plurality of web pages and to provide the plurality of web pages or other information to the web customers 105 over the various ISPs.
In one specific example, a personal computer 105a of the web customers 105 can communicate a request to a web page hosting computer (server 106, for example) for requesting a particular web page having predetermined content. The request can be communicated from the personal computer 105a to the web page hosting computer 106 over a number of different paths within network 101 (e.g., by path ABCD or path ABEFG).
The choice of path is determined automatically through the exchange of signaling information between networking devices along all paths traversing some combination of A,B,C,D,E,F,G. Network devices in ISP1 and ISP2 signal availability of a path to site 106 to each neighbor network, ISP3 and ISP4. This signalling may occur, for example, according to a routing protocol that defines methods by which network devices determine how to forward information. More particularly, ISP3 and ISP4 and other network devices of network 101 communicate routing protocol information amongst each other indicating their knowledge of the network.
Once the paths are established, messages (e.g., web page requests from customers in 105) can begin to travel to the servers in 106. In the path ABCD, ISP7 initially receives the request for the web page from the personal computer 105a and forwards the request to ISP3. Similarly, ISP3 for-wards the request for the web page to ISP I, which ultimately forwards the request to the web page hosting computer 106. Each of the ISP's also send control signals to the other ISPs. The control signals, includes among other things, information related to a return path from the site 106 to the requesting computer.
Referring further to FIG. 3, one problem occurs when an attacker computer system 107 of ISP5, for example, maliciously sends ISP4 erroneous or deceptive control signals. The deceptive control signals can include information indicating that ISP5 has the most efficient access to the web page hosting computer 106. In this example, the deceptive control signals would be communicated back to the personal computer 105a over the data path HIJK. In this instance, the personal computer's 105a request for the web page would not be received by the web page hosting site 106, because the request may be actually redirected to, for example, an attacker computer system 107 of ISP5 or to an incorrect destination. This may result in reduced access to the web page hosting computer 106, which can result in reduced business, lost sales and/or a general theft of service that the web page hosting site 106 would otherwise realize. This scenario is one type of what is referred to in the art as a Denial of Service (DoS) attack.
Conventional routing systems 103 (FIG. 1) have attempted to avoid erroneous control signal attacks, as described above, by employing various types of control signal encryption techniques to validate the integrity of the source of control signals. These control signals encryption techniques require that a number of public keys be distributed among the various ISPs for which the keys can be processed with other information residing on the various ISPs to encode and decode the control signals. However, this technique has not yet been implemented because of the complexity and associated costs related to the hardware and software necessary to encode and decode the control signals.
Other conventional routing systems 103 have attempted to avoid deceptive control signal attacks by employing a common Internet Routing Registry (“IRR”). In this technique, all of the ISPs are required to subscribe to the IRR and provide details of their policy and customer topology information. Using this topology information, providers can generate a number of access control lists (“ACLs”). The ACLs generally describe addresses of various ISPs for which a particular ISP (the ISP providing the ACL) will accept information. Thus, a particular ISP, which receives a control signal from another ISP can verify with the IRR that the particular ISP should accept or reject the control signal. However, this technique is limited because it requires all the various ISPs of the wide area network to subscribe to the IRR. There has only been limited acceptance of the IRR to date and therefore, limited effectiveness.
In addition to security concerns, another problem stems from the rate and volume of topology signaling information exchanged between ISPs. The volume and rate of change in signaled topology information poses significant network engineering management, planning and debugging challenges. As the signaling communication is automated, changes to network paths in response to failures or policy changes may occur without the knowledge or intervention of network operators.